#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 heihieyouheihei, Inc. All Rights Reserved 
#
# @Time    : 2024/9/23 9:00
# @Author  : Yuyun
# @File    : leetcode_79_单词搜索.py
# @IDE     : PyCharm
"""
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。
同一个单元格内的字母不允许被重复使用。

示例 1：
A B C E
S F C S
A D E E
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true
示例 3：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

提示：
m == board.length
n = board[i].length
1 <= m, n <= 6
1 <= word.length <= 15
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
"""

"""
visited[i][j] == 1，表示此单元格已经被使用
字符串首字母位置集合positions = [(x1, y1),(x2, y2),……]
根据首字母位置DFS深度优先遍历：
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]，相邻单元格【上，下、左、右】
    递归：搜索某个方向的单元格
    回溯：若该单元格四个方向找不到，则将对应visited[i][j] = 0并回溯至上一个节点，搜索另外方向，
    剪枝：某方向单元格字符！=目标字符 or visited[i][j] == 1，直接切换为另一个方向（仅遍历条件情况：方向单元格字符==目标字符 or visited[i][j] ！= 1）
    终止条件：某一首字母位置出发递归找到所有字符，结果为True；全部首字母出发均未找到所有字符，结果为False
"""

class Solution:
    # 检查坐标（x,y）是否在棋盘范围内，防止DFS检查坐标越界
    def in_bounds(self, x, y, row, column):
        return 0 <= x < row and 0 <= y < column

    def dfs(self, board, row, column, x, y, word, index, visited, res):
        #   DFS遍历完所有单词，均在单元格中找到时，修改结果res = True；其他保持默认res = False
        if index == len(word):
            res[0] = True
            return
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        #   遍历单元格的四个方位
        for d_x, d_y in directions:
            n_x, n_y = d_x + x, d_y + y
            if self.in_bounds(n_x, n_y, row, column):
                if board[n_x][n_y] == word[index] and not visited[n_x][n_y]:
                    visited [n_x][n_y] = 1
                    self.dfs(board,row, column, n_x, n_y, word, index + 1, visited, res)
                    #   找不到，回溯
                    visited [n_x][n_y] = 0
                #   单元格已经访问过 或者 单词不匹配；不做处理，保持默认res = False结果
            #   越界情况不统计

    def deal_with(self, board, word):
        #   行
        row = len(board)
        #   列
        column = len(board[0])
        #   访问数组
        visited = [[0] * column for _ in range(row)]
        #   首字母位置
        first_word_pos = []
        for i in range(row):
            for j in range(column):
                if board[i][j] == word[0]:
                    first_word_pos.append((i, j))
        #   首字母不在board中，直接返回False
        if not first_word_pos :
            return False
        #   对每个首字母位置进行DFS，DFS内从word[1:]开始
        res = [False]
        #   使用列表数据类型，函数传入列表作为参数，再在DFS中改变res的值——类似全局变量效果
        for x, y in first_word_pos:
            visited[x][y] = 1
            self.dfs(board, row, column, x, y, word, 1, visited, res)
            #   存在从某个首字母位置，可以找到完整字符串，则直接返回True
            if res[0] == True:
                return True
            visited[x][y] = 0
        #   所有首字母位置均找不到，则返回False
        return False
if __name__ == '__main__':
    try:
        #   初始化网格
        board = eval(input())
        word = input().strip()
        solution = Solution()
        result = solution.deal_with(board, word)
        print(result)
    except Exception as e:
        print(e)
